#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;

class Solution {
public:
    void toRPN(const string& s, size_t& i, vector<string>& v)
    {
        stack<char> flags;
        unordered_map<char, int> map = { {'+',1},{'-',1},{'*',2},{'/',2} };
        while (i < s.size())
        {
            if (isdigit(s[i]))
            {
                string num;
                while (i < s.size() && isdigit(s[i]))
                {
                    num += s[i++];
                }
                v.push_back(num);
            }
            else if (s[i] == '(')
            {
                ++i;
                toRPN(s, i, v);
            }
            else if (s[i] == ')')
            {
                while (!flags.empty())
                {
                    v.push_back(string(1, flags.top()));
                    flags.pop();
                }
                ++i;
                return;
            }
            else
            {
                if (flags.empty() || map[s[i]] > map[flags.top()])
                {
                    flags.push(s[i++]);
                }
                else
                {
                    char op = flags.top();
                    flags.pop();

                    v.push_back(string(1, op));
                }
            }
        }
        while (!flags.empty())
        {
            v.push_back(string(1, flags.top()));
            flags.pop();
        }
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        for (auto t : tokens)
        {
            if (t == "+" || t == "-" || t == "*" || t == "/")
            {
                int n1 = nums.top();
                nums.pop();
                int n2 = nums.top();
                nums.pop();
                switch (t[0])
                {
                case '+':
                    nums.push(n1 + n2);
                    break;
                case '-':
                    nums.push(n2 - n1);
                    break;
                case '*':
                    nums.push(n2 * n1);
                    break;
                case '/':
                    nums.push(n2 / n1);
                    break;
                }
            }
            else
            {
                nums.push(stoi(t));
            }
        }
        return nums.top();
    }

    int calculate(string s) {
        string news;
        for (auto ch : s)
        {
            if (ch != ' ')
                news += ch;
        }

        news.swap(s);
        news.clear();
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] != ')')))
                news += "0-";
            else
                news += s[i];
        }
        cout << news;
        vector<string> v;
        size_t i = 0;
        toRPN(news, i, v);
        return evalRPN(v);
    }

    int dis[10][10];
    int cnt = 0;
    int dics[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> Q;
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        memset(dis, -1, sizeof(dis));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 2)
                {
                    Q.emplace(i, j);
                    dis[i][j] = 0;
                }
                else if (grid[i][j])
                    ++cnt;
            }
        }
        while (!Q.empty())
        {
            int x= Q.front().first;
            int y = Q.front().second;
            Q.pop();
            for (int k = 0; k < 4; ++k)
            {
                int newx = x + dics[k][0], newy = y + dics[k][1];
                if (newx < 0 || newx >= m || newy < 0 || newy >= n || !grid[newx][newy] || ~dis[newx][newy])
                {
                    continue;
                }
                dis[newx][newy] = dis[x][y] + 1;
                Q.emplace(newx, newy);
                if (grid[newx][newy] == 1)
                {
                    --cnt;
                    ans = dis[newx][newy];
                    if (!cnt) break;
                }
            }
        }
        return cnt ? -1 : ans;
    }

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        bool visited[11][11] = { 0 };
        int dics[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
        int dic = 0;
        int m = matrix.size(), n = matrix[0].size();
        int total = m * n;
        vector<int> ans(total);
        int row = 0, col = 0;
        for (int i = 0; i < total; ++i)
        {
            ans[i] = matrix[row][col];
            visited[row][col] = true;
            int newrow = row + dics[dic][0], newcol = col + dics[dic][1];
            if (newrow < 0 || newrow >= m || newcol < 0 || newcol >= n || visited[newrow][newcol])
            {
                dic = (dic + 1) % 4;
            }
            row += dics[dic][0], col += dics[dic][1];
        }
        return ans;
    }

    vector<pair<int, int>> zero;
    void dfs(vector<vector<int>>& matrix)
    {
        for (auto& kv : zero)
        {
            for (int i = 0; i < matrix.size(); ++i)
            {
                matrix[i][kv.second] = 0;
            }
            for (int i = 0; i < matrix[0].size(); ++i)
            {
                matrix[kv.first][i] = 0;
            }
        }
    }

    void setZeroes(vector<vector<int>>& matrix) {
        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[0].size(); ++j)
            {
                if (matrix[i][j] == 0)
                    zero.push_back({ i,j });
            }
        }
        dfs(matrix);
    }

    int findWinningPlayer(vector<int>& skills, int k) {
        int winCnt = 0;
        int winIndex = 0;
        for (int i = 1; i < skills.size(); ++i)
        {
            if (winCnt == k) return winIndex;
            if (skills[i] > skills[winIndex])
            {
                winIndex = i;
                winCnt = 1;
            }
            else
            {
                ++winCnt;
            }
        }
        return winIndex;
    }

    class Node {
    public:
        int val;
        vector<Node*> children;

        Node() {}

        Node(int _val) {
            val = _val;
        }

        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };

    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> Q;
        int levelSize = 0;
        if (root)
        {
            Q.push(root);
            levelSize = 1;
        }
        vector<vector<int>> ret;
        while (!Q.empty())
        {
            vector<int> level;
            while (levelSize--)
            {
                Node* front = Q.front();
                Q.pop();
                level.push_back(front->val);
                vector<Node*> children = front->children;
                for (int i = 0; i < children.size(); ++i)
                {
                    Q.push(children[i]);
                }
            }
            ret.push_back(level);
            levelSize = Q.size();
        }
        return ret;
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
        
    };

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> Q;
        int levelSize = 0;
        if (root)
        {
            Q.push(root);
            levelSize = 1;
        }
        vector<vector<int>> ret;
        int flag = 1;
        while (!Q.empty())
        {
            vector<int> level;
            while (levelSize--)
            {
                TreeNode* front = Q.front();
                Q.pop();
                level.push_back(front->val);
                if (front->left)
                    Q.push(front->left);
                if (front->right)
                    Q.push(front->right);
            }
            if (flag == -1)
                reverse(level.begin(), level.end());
            ret.push_back(level);
            levelSize = Q.size();
            flag *= -1;
        }
        return ret;
    }

    bool visited[50][50] = { 0 };
    int dics[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
    int orginal;
    bool dfs(vector<vector<int>>& image, int i, int j, int color)
    {

        for (int k = 0; k < 4; ++k)
        {
            int x = i + dics[k][0], y = j + dics[k][1];
            if (x >= 0 && x < image.size() && y >= 0 && y < image[0].size() && !visited[x][y] && image[x][y] == orginal)
            {
                visited[x][y] = true;
                image[x][y] = color;
                if (dfs(image, x, y, color)) return true;
            }
        }
        return false;
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        orginal = image[sr][sc];
        visited[sr][sc] = true;
        dfs(image, sr, sc, color);
        image[sr][sc] = color;
        return image;
    }
};

int main()
{
    vector<string> v;
    size_t i = 0;
    string str1 = "1+2-3";
    string str2 = "1+2-(3*4+5)-7";
    Solution().toRPN(str2, i, v);
    for (auto& e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}